package com.leetcode.easy;

import com.leetcode.entity.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zfl
 * @Classname GetIntegerSectionNode
 * @Description 返回两个相交的单链表的交点
 * @Date 2020/10/3 20:20
 */
public class GetIntersectionNode {

    /**
     * @param headA
     * @param headB
     * @return ListNode
     * 执行用时：14 ms, 在所有 Java 提交中击败了6.62%的用户
     * 内存消耗：41.8 MB, 在所有 Java 提交中击败了35.60%的用户
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        Set<ListNode> setA = new HashSet<>();
        ListNode p1 = headA;
        while (p1 != null) {
            if(setA.contains(p1)) {
                break;
            }else {
                setA.add(p1);
                p1 = p1.next;
            }
        }
        Set<ListNode> setB = new HashSet<>();
        ListNode p2 = headB;
        while (p2 != null) {
            if(setA.contains(p2)) {
                return p2;
            }
            if(setB.contains(p2)) {
                break;
            }else {}
            setB.add(p2);
            p2 = p2.next;
        }
        return null;
    }

    /**
     * @param headA
     * @param headB
     * @return ListNode
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
     * 内存消耗：41.9 MB, 在所有 Java 提交中击败了16.77%的用户
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }

        return p1;
    }
}
